package algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 118. 杨辉三角
 * @author Panbo Guo
 * @date 2021/7/20
 */
public class T00118 {

    public static void main(String[] args) {
        System.out.println(new Solution().generate(5));
    }

    static class Solution {
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> list = new ArrayList<>(numRows);
            if (numRows > 0) {
                List<Integer> row = new ArrayList<>(1);
                row.add(1);
                list.add(row);
            }
            if (numRows > 1) {
                List<Integer> row = new ArrayList<>(1);
                row.add(1);
                row.add(1);
                list.add(row);
            }

            if (numRows > 2) {
                for (int i = 2; i < numRows; i++) {
                    List<Integer> beforeRow = list.get(i - 1);
                    List<Integer> curRow = new ArrayList<>(i + 1);
                    curRow.add(1);
                    for (int j = 1; j < i; j++) {
                        curRow.add(beforeRow.get(j - 1) + beforeRow.get(j));
                    }
                    curRow.add(1);
                    list.add(curRow);
                }
            }
            return list;
        }
    }
}
